package 分类.二分;

import java.util.Arrays;
import java.util.Comparator;

public class 俄罗斯套娃信封问题 {
    public int maxEnvelopes(int[][] envelopes) {
        if(envelopes.length==0) return 0;
        Arrays.sort(envelopes, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if(o1[0]==o2[0]){
                    return o2[1]-o1[1];
                }else {
                    return o1[0]-o2[0];
                }
            }
        });

        //接下来就是求最大连续递增序列
        int[] lie=new int[envelopes.length];
        Arrays.fill(lie,1);
        int res=0;
        //以i结尾的最大递增数
        for (int i=0;i<lie.length;i++){
            for (int j=0;j<i;j++){
                if(envelopes[i][1]>envelopes[j][1]){
                    lie[i]=Math.max(lie[i],lie[j]+1);
                }
            }
            res=Math.max(res,lie[i]);
        }


        return res;

    }
}
